﻿/*******************************************************************************
*                                                                              *
* Author    :  Angus Johnson                                                   *
* Version   :  6.4.2                                                           *
* Date      :  27 February 2017                                                *
* Website   :  http://www.angusj.com                                           *
* Copyright :  Angus Johnson 2010-2017                                         *
*                                                                              *
* License:                                                                     *
* Use, modification & distribution is subject to Boost Software License Ver 1. *
* http://www.boost.org/LICENSE_1_0.txt                                         *
*                                                                              *
* Attributions:                                                                *
* The code in this library is an extension of Bala Vatti's clipping algorithm: *
* "A generic solution to polygon clipping"                                     *
* Communications of the ACM, Vol 35, Issue 7 (July 1992) pp 56-63.             *
* http://portal.acm.org/citation.cfm?id=129906                                 *
*                                                                              *
* Computer graphics and geometric modeling: implementation and algorithms      *
* By Max K. Agoston                                                            *
* Springer; 1 edition (January 4, 2005)                                        *
* http://books.google.com/books?q=vatti+clipping+agoston                       *
*                                                                              *
* See also:                                                                    *
* "Polygon Offsetting by Computing Winding Numbers"                            *
* Paper no. DETC2005-85513 pp. 565-575                                         *
* ASME 2005 International Design Engineering Technical Conferences             *
* and Computers and Information in Engineering Conference (IDETC/CIE2005)      *
* September 24-28, 2005 , Long Beach, California, USA                          *
* http://www.me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf              *
*                                                                              *
*******************************************************************************/

/*******************************************************************************
*                                                                              *
* This is a translation of the Delphi Clipper library and the naming style     *
* used has retained a Delphi flavour.                                          *
*                                                                              *
*******************************************************************************/

/*******************************************************************************
* Boost Software License - Version 1.0 - August 17th, 2003                     *
*                                                                              *
* Permission is hereby granted, free of charge, to any person or organization  *
* obtaining a copy of the software and accompanying documentation covered by   *
* this license (the "Software") to use, reproduce, display, distribute,        *
* execute, and transmit the Software, and to prepare derivative works of the   *
* Software, and to permit third-parties to whom the Software is furnished to   *
* do so, all subject to the following:                                         *
*                                                                              *
* The copyright notices in the Software and this entire statement, including   *
* the above license grant, this restriction and the following disclaimer,      *
* must be included in all copies of the Software, in whole or in part, and     *
* all derivative works of the Software, unless such copies or derivative       *
* works are solely in the form of machine-executable object code generated by  *
* a source language processor.                                                 *
*                                                                              *
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR   *
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,     *
* FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT    *
* SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE    *
* FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,  *
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER  *
* DEALINGS IN THE SOFTWARE.                                                    *
*******************************************************************************/

/*******************************************************************************
*                                                                              *
* Code modified for PdfPig                                                     *
*                                                                              *
*******************************************************************************/
namespace UglyToad.PdfPig.Geometry.ClipperLibrary
{
    //------------------------------------------------------------------------------
    // Int128 struct (enables safe math on signed 64bit integers)
    // eg Int128 val1((long)9223372036854775807); //ie 2^63 -1
    //    Int128 val2((long)9223372036854775807);
    //    Int128 val3 = val1 * val2;
    //    val3.ToString => "85070591730234615847396907784232501249" (8.5e+37)
    //------------------------------------------------------------------------------

    internal struct ClipperInt128
    {
        private long hi;
        private ulong lo;

        public ClipperInt128(long _lo)
        {
            lo = (ulong)_lo;
            if (_lo < 0) hi = -1;
            else hi = 0;
        }

        public ClipperInt128(long _hi, ulong _lo)
        {
            lo = _lo;
            hi = _hi;
        }

        public ClipperInt128(ClipperInt128 val)
        {
            hi = val.hi;
            lo = val.lo;
        }

        public bool IsNegative()
        {
            return hi < 0;
        }

        public static bool operator ==(ClipperInt128 val1, ClipperInt128 val2)
        {
            if ((object) val1 == (object) val2)
            {
                return true;
            }

            return (val1.hi == val2.hi && val1.lo == val2.lo);
        }

        public static bool operator !=(ClipperInt128 val1, ClipperInt128 val2)
        {
            return !(val1 == val2);
        }

        public override bool Equals(object? obj)
        {
            if (!(obj is ClipperInt128 i128))
            {
                return false;
            }

            return (i128.hi == hi && i128.lo == lo);
        }

        public override int GetHashCode()
        {
            return hi.GetHashCode() ^ lo.GetHashCode();
        }

        public static bool operator >(ClipperInt128 val1, ClipperInt128 val2)
        {
            if (val1.hi != val2.hi)
                return val1.hi > val2.hi;
            else
                return val1.lo > val2.lo;
        }

        public static bool operator <(ClipperInt128 val1, ClipperInt128 val2)
        {
            if (val1.hi != val2.hi)
                return val1.hi < val2.hi;
            else
                return val1.lo < val2.lo;
        }

        public static ClipperInt128 operator +(ClipperInt128 lhs, ClipperInt128 rhs)
        {
            lhs.hi += rhs.hi;
            lhs.lo += rhs.lo;
            if (lhs.lo < rhs.lo) lhs.hi++;
            return lhs;
        }

        public static ClipperInt128 operator -(ClipperInt128 lhs, ClipperInt128 rhs)
        {
            return lhs + -rhs;
        }

        public static ClipperInt128 operator -(ClipperInt128 val)
        {
            if (val.lo == 0)
                return new ClipperInt128(-val.hi, 0);
            else
                return new ClipperInt128(~val.hi, ~val.lo + 1);
        }

        public static explicit operator double(ClipperInt128 val)
        {
            const double shift64 = 18446744073709551616.0; //2^64
            if (val.hi < 0)
            {
                if (val.lo == 0)
                {
                    return (double)val.hi * shift64;
                }

                return -(double)(~val.lo + ~val.hi * shift64);
            }
            
            return (double)(val.lo + val.hi * shift64);
        }

        //nb: Constructing two new Int128 objects every time we want to multiply longs  
        //is slow. So, although calling the Int128Mul method doesn't look as clean, the 
        //code runs significantly faster than if we'd used the * operator.

        public static ClipperInt128 Int128Mul(long lhs, long rhs)
        {
            bool negate = (lhs < 0) != (rhs < 0);
            if (lhs < 0) lhs = -lhs;
            if (rhs < 0) rhs = -rhs;
            ulong int1Hi = (ulong)lhs >> 32;
            ulong int1Lo = (ulong)lhs & 0xFFFFFFFF;
            ulong int2Hi = (ulong)rhs >> 32;
            ulong int2Lo = (ulong)rhs & 0xFFFFFFFF;

            //nb: see comments in clipper.pas
            ulong a = int1Hi * int2Hi;
            ulong b = int1Lo * int2Lo;
            ulong c = int1Hi * int2Lo + int1Lo * int2Hi;

            ulong lo;
            long hi;
            hi = (long)(a + (c >> 32));

            unchecked { lo = (c << 32) + b; }
            if (lo < b) hi++;
            ClipperInt128 result = new ClipperInt128(hi, lo);
            return negate ? -result : result;
        }
    }
}